//给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[
//i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
//
//
//
// 示例:
//
//
//输入: [1,2,3,4,5]
//输出: [120,60,40,30,24]
//
//
//
// 提示：
//
//
// 所有元素乘积之和不会溢出 32 位整数
// a.length <= 100000
//
//
// Related Topics 数组 前缀和 👍 327 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
//?
function constructArr(a: number[]): number[] {

    /**
     * @param {number[]} a
     * @return {number[]}
     */
    /*
    ? 从左到右遍历构建当前元素之前的的左边的所有乘积
    ? 从右向左遍历，用一个变量来存当前元素右边元素的所有乘积
    ? 当前结果集中任何一个元素 = 其左边所有元素的乘积 * 其右边所有元素的乘积
     */
    let n = a.length;
    //? 非空判定
    if (!n) return [];
    //? 结果集中任何一个元素 = 其左边所有元素的乘积 * 其右边所有元素的乘积
    let result = new Array(n).fill(1);
    let rightAccu = 1;
    for (let i = 1; i < n; i++) {
        //? 构建左边的乘积并保存在结果集中
        result[i] = result[i - 1] * a[i - 1];
    }
    console.log(result)
    for (let i = n - 2; i >= 0; i--) {
        //? 构建右边乘积，以a = [1, 2, 3, 4, 5]举例，这里的temp会分别等于5、20、60、120
        rightAccu *= a[i + 1];
        //? 乘以左边的乘积
        result[i] *= rightAccu;
    }
    return result;


};
//leetcode submit region end(Prohibit modification and deletion)
function constructArr2(arr: number[]): number[] {
    if(arr.length < 1) return [];
    const res:number[] = new Array(arr.length);
    const dpL:number[] = new Array(arr.length);
    const dpR:number[] = new Array(arr.length);

    dpL[0] = 1;
    dpR[arr.length - 1] = 1;

    for(let i = 1; i < arr.length; i++){
        dpL[i] = dpL[i - 1] * arr[i - 1];
    }
    for(let i = arr.length - 2; i >= 0; i--){
        dpR[i] = dpR[i + 1] * arr[i + 1];
    }
    console.log(dpL,dpR)
    for(let i = 0; i < arr.length; i++){
        res[i] = dpL[i] * dpR[i];
    }
    return res;
};
